The invention relates to a method and an apparatus for determining a route for a navigation system and/or a driver assistance system. The invention also relates to a method for determining correction values for a route calculation algorithm and to a system and a computer program product.
In vehicle navigation systems, the so-called A* algorithm is used in many cases to calculate the route. This algorithm is used to calculate a shortest path between a starting node and one or more arbitrary nodes in a graph with a positive edge weight. In graph theory, a graph is a set of points, the points partially being connected to one another by means of so-called edges. The points are also called nodes. The edges are also referred to as lines or connections. The shape of the points and edges does not play a role in graph theory. In graph theory, a real number assigned to the respective edge is referred to as the edge weight. The real number may represent, for example, a distance, a time period or a gasoline consumption.
The A* algorithm uses an estimation function (heuristics) in order to search in a targeted manner and therefore to reduce the run-time. However, if the estimation function does not represent the real route and/or path conditions in an area with sufficient accuracy, the calculation of the optimum route may take a very long time.
The object on which the invention is based is to provide a method and an apparatus for determining a route, a method for determining correction values for a route calculation algorithm and a system and a computer program product which contribute to increasing efficiency of the route determination, in particular accelerating the route determination.
According to a first aspect of the invention, a method is provided for determining correction values for a route calculation algorithm on the basis of digital map data for a route network and/or a path network in a predefined area. In this case, the digital map data include respective nodes in the area and connections between the respective nodes in the area. The digital map data also include respective edge costs for the respective connections between the nodes. The area is subdivided, in a predefined manner, into a plurality of tiles, for which correction values are determined. One of the tiles in the area is respectively determined as the starting tile and the respective remaining tiles are determined as reference tiles. Special nodes are predefined, which special nodes are arranged in the starting tile and form a true or artificial subset of all nodes in the starting tile, and special nodes being predefined, which special nodes are arranged in the respective reference tile and form a true or artificial subset of all nodes in the respective reference tile. A correction value is determined for the respective starting tile with respect to one of the reference tiles in each case in such a manner that a cost ratio is respectively determined for each special node in the respective starting tile with respect to each special node in the reference tile on the basis of the edge costs of the connections which lie between the respective special node in the starting tile and the respective special node in the reference tile and represent an optimum route between the respective special node in the starting tile and the respective special node in the reference tile. The cost ratio is also determined on the basis of a heuristic value for the respective special node in the starting tile with respect to the respective special node in the reference tile. A mean value is determined on the basis of the determined cost ratios. The correction value for the starting tile is determined with respect to the respective reference tile on the basis of the mean value.
Predefining the special nodes in the respective starting tile and the special nodes in the respective reference tile means that the number of correction values to be calculated remains within limits but it is possible to ensure at the same time that sufficient statistical relevance or accuracy of the correction values can be ensured. This advantageously makes it possible to determine the correction values with sufficient accuracy, with the result that subsequent route determination can be carried out more efficiently. The special nodes can be selected in a predefined manner, in particular. These selected nodes can be selected, for example, stochastically and/or on the basis of at least one predefined rule.
The correction values can be advantageously determined independently of current route determination, for example during map compiling.
The respective cost ratio is a direct measure of a discrepancy between the heuristic value for the respective special node in the starting tile with respect to the respective special node in the reference tile and the sum of the edge costs of an optimum route from the respective special node in the starting tile to the respective special node in the reference tile.
Depending on requirements, a different number of special nodes can respectively be selected for the starting tile and/or the respective reference tiles. An additionally required need for storage space for storing the correction values can therefore be kept suitably low.
In this case, the mean value is based on a calculation rule which is used to calculate a further number from two or more numbers, which further number lies between the given numbers.
The edge costs and the estimated costs have a predefined correspondence. The edge costs represent a value of a weighting function. The weighting function weights respective individual edge costs of the respective connection, for example route length costs and/or journey time costs, in a predefined manner. The estimated costs represent the value of an estimation function which weights estimated individual costs in a predefined manner similar to the weighting function. The optimum route is optimum with respect to the edge costs.
The heuristic value is determined using an estimation function which is also called heuristics. The estimation function may include, for example, a function for determining a shortest distance between two points in a predefined two-dimensional coordinate system (Euclidean distance). The prerequisite for the A* algorithm is that the estimation function is permissible. The estimation function is permissible if the respective heuristic value does not exceed the respective sum of the edge costs of the connections of the optimum route between two nodes to be considered. That is to say, the respective heuristic value must always be in the range [0; w] if w respectively denotes the sum of the edge costs of the connections of the optimum route between the two nodes to be considered. The respective correction values can therefore be determined on the basis of adapted mean values if necessary, with the result that it can be ensured that the permissibility prerequisites of the A* algorithm are also complied with when using the correction values. For example, the respective mean values can be adapted by dividing them by a predefined factor which is greater than 1.
In one advantageous refinement of the first aspect of the invention, the digital map data include the respective positions of the nodes in the area. The heuristic value for the respective special node in the starting tile with respect to the respective special node in the reference tile is determined on the basis of the position of the respective special node in the starting tile and the position of the respective special node in the reference tile. This advantageously makes it possible to save storage capacity.
In another advantageous refinement of the first aspect of the invention, the digital map data includes predefined heuristic values for the respective nodes with respect to the respective other nodes in the area which each represent estimated costs from one node in each case to the other node in each case, and the heuristic value for the respective special node in the starting tile with respect to the respective special node in the reference tile is therefore predefined. This advantageously makes it possible to save computing capacity when calculating the correction values.
In another advantageous refinement of the first aspect of the invention, the heuristic value for the respective special node in the starting tile with respect to the respective special node in the reference tile represents the Euclidean distance between the respective special node in the starting tile and the respective special node in the reference tile. This makes it possible to easily determine the correction values.
In another advantageous refinement of the first aspect, the mean value of the cost ratios represents an arithmetic mean value of the cost ratios. This has the advantage that the respective correction values can be easily provided.
According to a second and a third aspect of the invention, a method and a corresponding apparatus for determining a route for a navigation system and/or a driver assistance system are provided. The navigation system and/or driver assistance system is assigned at least one storage unit for storing digital map data for a route network and/or path network in a predefined area. In this case, the digital map data include respective nodes in the area and connections between the respective nodes in the area. The digital map data also include respective edge costs for the respective connections between the nodes, and a set of correction values determined in accordance with the first aspect. The route from a predefined starting node to a predefined destination node is determined on the basis of a predefined route criterion and on the basis of the digital map data stored in the storage unit in such a manner that, for a possible expansion of a respective current node, total costs are determined for the current node on the basis of a sum of edge costs of an optimum route from the starting node to the current node and a destination-node-based heuristic value for the current node and a destination-node-based correction value. The destination-node-based heuristic value represents respectively estimated costs from the current node to the destination node. The destination-node-based correction value is selected from the set of correction values on the basis of the current node and the destination node.
Advantageous refinements of the first aspect of the invention also apply here to the second and third aspects.
The data relating to the determined route can be forwarded to the navigation system for optically and/or acoustically signaling the determined route, for example on a display, and/or for determining and outputting driving instructions. Additionally or alternatively, the data may be forwarded to the driver assistance system, the predefined driver assistance system being designed to control predefined vehicle functions of a vehicle on the basis of the determined data relating to the route.
The correction values are preferably determined in advance. The respective destination-node-based correction values are at least one subset of the stored correction values.
The respective destination-node-based heuristic value can be assessed, for example, using the destination-node-based correction value. For example, if the destination-node-based heuristic value does not represent the real route and/or path conditions in the area with sufficient accuracy, the destination-node-based heuristic value may have an excessively small value. This can be at least partially compensated for by means of the assessment using the destination-node-based correction value. In comparison with the determination of the route without correction values, the optimum route can be determined with considerably fewer calculation steps when using the correction values.
In this case, the optimum route is optimum with respect to the predefined route criterion. Expanding a node means that, starting from this node, the total costs of further nodes having a connection to this node are determined. The route can be determined, for example, according to an A* algorithm. In the A* algorithm, the node having the lowest total costs is respectively expanded next. For the decision regarding whether the current node is expanded in the next step, the total costs of the current node are determined and compared with the total costs of further possible expansion nodes.
The edge costs and the estimated costs have a predefined correspondence. The edge costs represent a value of a weighting function. The weighting function weights respective individual edge costs of the respective connection, for example route length costs and/or journey time costs, in a predefined manner. The estimated costs represent the value of an estimation function which weights estimated individual costs, for example estimated route length residual costs from a current node to the destination node and/or estimated journey time residual costs from the current node to the destination node, in a predefined manner similar to the weighting function. In a simplified case, the edge costs may represent, for example, the route length costs of the respective connection and the estimated costs may represent, for example, the estimated route length residual costs, for example the Euclidean distance, between the current node and the destination node.
In one advantageous refinement of the second and third aspects of the invention, the digital map data include the respective positions of the nodes in the area, and the destination-node-based heuristic value is determined on the basis of the position of the current node and the position of the destination node. A storage capacity of the storage unit can therefore be advantageously kept low.
In another advantageous refinement of the second and third aspects of the invention, the digital map data include predefined heuristic values for the respective nodes with respect to the respective other nodes in the area which each represent estimated costs from one node in each case to the other node in each case, and the destination-node-based heuristic value is therefore predefined. This advantageously makes it possible to save computing capacity since the destination-node-based heuristic values can be determined in advance and therefore independently of a current route calculation.
In another advantageous refinement of the second and third aspects of the invention, the respective destination-node-based heuristic value represents the Euclidean distance between the current node and the destination node. The destination-node-based heuristic values can therefore be advantageously determined in a very simple manner. Furthermore, the Euclidean distance to the destination is a monotonous estimation function (heuristics) and therefore complies with, in particular, the reliability prerequisite for the A* algorithm.
According to a fourth aspect of the invention, a system is provided which has a storage unit and an apparatus according to the third aspect and in which the storage unit stores digital map data for a route network and/or a path network in a predefined area. The apparatus is coupled to the storage unit using signaling and is designed to read the digital map data from the storage unit. In this case, the digital map data include respective nodes in the area and connections between the respective nodes in the area. The digital map data also include respective edge costs for the respective connections. Furthermore, the digital map data comprise a set of correction values determined in accordance with the first aspect.
Advantageous refinements of the first, second and third aspects of the invention also apply in this case to the fourth aspect of the invention.
According to a fifth aspect of the invention, a computer program product is provided comprising executable program code, the program code carrying out the steps of the method according to the first aspect during execution by a data processing apparatus. Advantageous refinements of the first aspect also apply in this case to the fifth aspect.
Other objects, advantages and novel features of the present invention will become apparent from the following detailed description of one or more preferred embodiments when considered in conjunction with the accompanying drawings.